SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Simple precedence parser</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Simple precedence grammar</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>simple precedence grammar</b> is a <a href="Context-free_grammar" title="Context-free grammar">context-free</a> <a href="Formal_grammar" title="Formal grammar">formal grammar</a> that can be parsed with a <a href="Simple_precedence_parser" class="mw-redirect" title="Simple precedence parser">simple precedence parser</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The concept was first created in 1964 by <a href="https://fr.wikipedia.org/wiki/Claude_Pair" class="extiw external" title="fr:Claude Pair">Claude Pair</a>,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> and was later rediscovered, from ideas due to <a href="Robert_W._Floyd" title="Robert W. Floyd">Robert Floyd</a>, by <a href="Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a> and Helmut Weber who published a paper, entitled <i>EULER: a generalization of ALGOL, and its formal definition</i>, published in 1966 in the <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

<p>G = (<i>N</i>, Σ, <i>P</i>, <i>S</i>) is a simple precedence grammar if all the production rules in <i>P</i> comply with the following constraints:

</p>

<ul><li>There are no <a href="Erasing_rule" class="mw-redirect" title="Erasing rule">erasing rules</a> (ε-productions)</li>

<li>There are no <a href="Useless_rules" class="mw-redirect" title="Useless rules">useless rules</a> (unreachable symbols or unproductive rules)</li>

<li>For each pair of symbols <i>X</i>, <i>Y</i> (<i>X</i>, <i>Y</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \in }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \in }</annotation>

</semantics>

</math></span><img src="./6fe4d5b0a594c1da89b5e78e7dfbeed90bdcc32f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:1.843ex;" alt="{\displaystyle \in }" loading="lazy"></span> (<i>N</i> ∪ Σ)) there is only one <a href="Wirth%E2%80%93Weber_precedence_relationship" class="mw-redirect" title="Wirth–Weber precedence relationship">Wirth–Weber precedence relation</a>.</li>

<li>G is uniquely inversible</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to aSSb|c}</annotation>

</semantics>

</math></span><img src="./1951c04855860daff1bdd5d194e82fcb3aa40387.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.993ex; height:2.843ex;" alt="{\displaystyle S\to aSSb|c}" loading="lazy"></span></dd></dl>

<dl><dt>precedence table</dt>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mover>

</mover>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

<mover>

</mover>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mover>

</mover>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&{\dot {=}}&\lessdot &{\dot {=}}&\lessdot &\\a&{\dot {=}}&\lessdot &&\lessdot &\\b&&\gtrdot &&\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}</annotation>

</semantics>

</math></span><img src="./a86bddb5dff53ae64d6855abdd4f42787e239449.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.505ex; width:24.762ex; height:20.176ex;" alt="{\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&{\dot {=}}&\lessdot &{\dot {=}}&\lessdot &\\a&{\dot {=}}&\lessdot &&\lessdot &\\b&&\gtrdot &&\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Simple_precedence_parser">Simple precedence parser</h2></div>

<p>A <b>simple precedence parser</b> is a type of <a href="Bottom-up_parser" class="mw-redirect" title="Bottom-up parser">bottom-up parser</a> for <a href="Context-free_grammars" class="mw-redirect" title="Context-free grammars">context-free grammars</a> that can be used only by .

</p><p>The implementation of the parser is quite similar to the generic <a href="Bottom-up_parser" class="mw-redirect" title="Bottom-up parser">bottom-up parser</a>. A stack is used to store a viable prefix of a <a href="Sentential_form" class="mw-redirect" title="Sentential form">sentential form</a> from a <a href="Rightmost_derivation" class="mw-redirect" title="Rightmost derivation">rightmost derivation</a>. The symbols ⋖, ≐ and ⋗ are used to identify the <b>pivot</b>, and to know when to <b>Shift</b> or when to <b>Reduce</b>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Implementation">Implementation</h3></div>

<ul><li>Compute the <a href="Wirth%E2%80%93Weber_precedence_relationship" class="mw-redirect" title="Wirth–Weber precedence relationship">Wirth–Weber precedence relationship</a> table for a grammar with initial symbol S.</li>

<li>Initialize a stack with the <b>starting marker</b> $.</li>

<li>Append an <b>ending marker</b> $ to the string being parsed (<b>Input</b>).</li>

<li>Until Stack equals "$ S" and Input equals "$"

<ul><li>Search the table for the relationship between Top(stack) and NextToken(Input)</li>

<li>if the relationship is ⋖ or ≐

<ul><li><b>Shift</b>:</li>

<li>Push(Stack, relationship)</li>

<li>Push(Stack, NextToken(Input))</li>

<li>RemoveNextToken(Input)</li></ul></li>

<li>if the relationship is ⋗

<ul><li><b>Reduce</b>:</li>

<li>SearchProductionToReduce(Stack)</li>

<li>Remove the Pivot from the Stack</li>

<li>Search the table for the relationship between the nonterminal from the production and first symbol in the stack (Starting from top)</li>

<li>Push(Stack, relationship)</li>

<li>Push(Stack, Non terminal)</li></ul></li></ul></li></ul>

<p>SearchProductionToReduce (Stack)

</p>

<ul><li>Find the topmost ⋖ in the stack; this and all the symbols above it are the <b>Pivot</b>.</li>

<li>Find the production of the grammar which has the <b>Pivot</b> as its right side.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

<p>Given following language, which can parse arithmetic expressions with the multiplication and addition operations:

</p>

<pre>E --> E + T' | T'

T' --> T

T --> T * F | F

F --> ( E' ) | num

E' --> E

</pre>

<p><b>num</b> is a terminal, and the <a href="Lexer_(computer_science)" class="mw-redirect" title="Lexer (computer science)">lexer</a> parse any integer as <b>num</b>; <b>E</b> represents an arithmetic expression, <b>T</b> is a term and <b>F</b> is a factor.

</p><p>and the Parsing table:

</p>

<th>$

</th></tr>

<tr>

<th>E

</th>

<td>

</td></tr>

<tr>

<th>E'

</th>

<td>

</td></tr>

<tr>

<th>T

</th>

<td>⋗

</td></tr>

<tr>

<th>T'

</th>

<td>⋗

</td></tr>

<tr>

<th>F

</th>

<td>⋗

</td></tr>

<tr>

<th>+

</th>

<td>

</td></tr>

<tr>

<th>*

</th>

<td>

</td></tr>

<tr>

<th>(

</th>

<td>

</td></tr>

<tr>

<th>)

</th>

<td>⋗

</td></tr>

<tr>

<th>num

</th>

<td>⋗

</td></tr>

<tr>

<th>$

</th>

<td>

</td></tr></tbody></table>

<table class="wikitable" style="font-family:monospace"><tbody><tr style="vertical-align:top"><th scope="col"> STACK</th><th scope="col"> PRECEDENCE</th><th scope="col" style="text-align:right;"> INPUT</th><th scope="col"> ACTION</th></tr><tr style="vertical-align:top"><td> $</td><td> ⋖</td><td style="text-align:right;"> 2 * ( 1 + 3 )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ 2</td><td> ⋗</td><td style="text-align:right;"> * ( 1 + 3 )$</td><td> REDUCE (F -> num)</td></tr><tr style="vertical-align:top"><td> $ ⋖ F</td><td> ⋗</td><td style="text-align:right;"> * ( 1 + 3 )$</td><td> REDUCE (T -> F)</td></tr><tr style="vertical-align:top"><td> $ ⋖ T</td><td> ≐</td><td style="text-align:right;"> * ( 1 + 3 )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ *</td><td> ⋖</td><td style="text-align:right;"> ( 1 + 3 )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ (</td><td> ⋖</td><td style="text-align:right;"> 1 + 3 )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ⋖ 1</td><td> ⋗</td><td style="text-align:right;"> + 3 )$</td><td> REDUCE 4× (F -> num) (T -> F) (T' -> T) (E ->T ')</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ⋖ E</td><td> ≐</td><td style="text-align:right;"> + 3 )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ +</td><td> ⋖</td><td style="text-align:right;"> 3 )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3</td><td> ⋗</td><td style="text-align:right;"> )$</td><td> REDUCE 3× (F -> num) (T -> F) (T' -> T)</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T</td><td> ⋗</td><td style="text-align:right;"> )$</td><td> REDUCE 2× (E -> E + T) (E' -> E)</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ≐ E'</td><td> ≐</td><td style="text-align:right;"> )$</td><td> SHIFT</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )</td><td> ⋗</td><td style="text-align:right;"> $</td><td> REDUCE (F -> ( E' ))</td></tr><tr style="vertical-align:top"><td> $ ⋖ T ≐ * ≐ F</td><td> ⋗</td><td style="text-align:right;"> $</td><td> REDUCE (T -> T * F)</td></tr><tr style="vertical-align:top"><td> $ ⋖ T</td><td> ⋗</td><td style="text-align:right;"> $</td><td> REDUCE 2× (T' -> T) (E -> T')</td></tr><tr style="vertical-align:top"><td> $ ⋖ E</td><td></td><td style="text-align:right;"> $</td><td> ACCEPT</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Wirth–Weber_precedence_relationship">Wirth–Weber precedence relationship</h2></div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <i>Wirth–Weber relationship</i> between a pair of symbols <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V_{t}\cup V_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (V_{t}\cup V_{n})}</annotation>

</semantics>

</math></span><img src="./9f291fec596f1b1aa3ee5de50476b9c85245be71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.147ex; height:2.843ex;" alt="{\displaystyle (V_{t}\cup V_{n})}" loading="lazy"></span> is necessary to determine if a <a href="Formal_grammar" title="Formal grammar">formal grammar</a> is a . In such a case, the <a href="Simple_precedence_parser" class="mw-redirect" title="Simple precedence parser">simple precedence parser</a> can be used. The relationship is named after computer scientists <a href="Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a> and Helmut Weber.

</p><p>The goal is to identify when the viable prefixes have the <i>pivot</i> and must be reduced. A <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gtrdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gtrdot }</annotation>

</semantics>

</math></span><img src="./7ade4309e8e12df271a3a66cda676411771e74fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \gtrdot }" loading="lazy"></span> means that the <i>pivot</i> is found, a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lessdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lessdot }</annotation>

</semantics>

</math></span><img src="./48abe158799d6c5ee0a960cec7e5321a5bf0ad61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \lessdot }" loading="lazy"></span> means that a potential <i>pivot</i> is starting, and a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \doteq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \doteq }</annotation>

</semantics>

</math></span><img src="./de69082f1885891812d259864e762e1543db2d6a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.307ex; margin-bottom: -0.478ex; width:1.808ex; height:2.009ex;" alt="{\displaystyle \doteq }" loading="lazy"></span> means that a relationship remains in the same <i>pivot</i>.

</p>

/* start https://en.wikipedia.org/ */

@media all and (max-width:720px){body.skin-minerva .mw-parser-output .tocright{display:none}.mw-parser-output .tocright{width:100%!important}}@media all and (min-width:720px){.mw-parser-output .tocright{float:right;clear:right;width:auto;margin:0 0 0.5em 1em}.mw-parser-output .tocright-clear-left{clear:left}.mw-parser-output .tocright-clear-both{clear:both}.mw-parser-output .tocright-clear-none{clear:none}}

/* end https://en.wikipedia.org/ */

</style><div class="tocright"><meta property="mw:PageProp/toc"></div>

<div class="mw-heading mw-heading3"><h3 id="Formal_definition_2">Formal definition</h3></div>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=\langle V_{n},V_{t},S,P\rangle }</annotation>

</semantics>

</math></span><img src="./4a2e09aaea79fe1c559532c175bee74f7f679d2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.836ex; height:2.843ex;" alt="{\displaystyle G=\langle V_{n},V_{t},S,P\rangle }" loading="lazy"></span>

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./2be7a27a0a27fa1064a6001f0761005c6b28cd6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -22.338ex; width:38.592ex; height:45.843ex;" alt="{\displaystyle {\begin{aligned}X\doteq Y&\iff {\begin{cases}A\to \alpha XY\beta \in P\\A\in V_{n}\\\alpha ,\beta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\lessdot Y&\iff {\begin{cases}A\to \alpha XB\beta \in P\\B\Rightarrow ^{+}Y\gamma \\A,B\in V_{n}\\\alpha ,\beta ,\gamma \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\end{cases}}\\X\gtrdot Y&\iff {\begin{cases}A\to \alpha BY\beta \in P\\B\Rightarrow ^{+}\gamma X\\Y\Rightarrow ^{*}a\delta \\A,B\in V_{n}\\\alpha ,\beta ,\gamma ,\delta \in (V_{n}\cup V_{t})^{*}\\X,Y\in (V_{n}\cup V_{t})\\a\in V_{t}\end{cases}}\end{aligned}}}" loading="lazy"></span></dd></dl></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Precedence_relations_computing_algorithm">Precedence relations computing algorithm</h3></div>

<p>We will define three sets for a symbol:

</p>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./e4a17a30bb3a5344f8a7a643b71f826151c02ca8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.903ex; margin-bottom: -0.268ex; width:38.372ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}\mathrm {Head} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}Y\alpha \}\\\mathrm {Tail} ^{+}(X)&=\{Y\mid X\Rightarrow ^{+}\alpha Y\}\\\mathrm {Head} ^{*}(X)&=(\mathrm {Head} ^{+}(X)\cup \{X\})\cap V_{t}\end{aligned}}}" loading="lazy"></span>

<dl><dd>Head<sup>*</sup>(<i>X</i>) is <i>X</i> if <i>X</i> is a terminal, and if <i>X</i> is a non-terminal, Head<sup>*</sup>(<i>X</i>) is the set with only the terminals belonging to Head<sup>+</sup>(<i>X</i>). This set is equivalent to <b>First-set</b> or <b>Fi(<i>X</i>)</b> described in <a href="LL_parser" title="LL parser">LL parser</a>.</dd>

<dd>Head<sup>+</sup>(<i>X</i>) and Tail<sup>+</sup>(<i>X</i>) are ∅ if <i>X</i> is a terminal.</dd></dl></dd></dl>

<p>The pseudocode for computing relations is:

</p>

<ul><li>RelationTable := ∅</li>

<li>For each production <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\to \alpha \in P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\to \alpha \in P}</annotation>

</semantics>

</math></span><img src="./476d69d9e70ceb97d84e1eb55675dedcc135c434.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.431ex; height:2.176ex;" alt="{\displaystyle A\to \alpha \in P}" loading="lazy"></span>

<ul><li>For each two adjacent symbols <span class="texhtml mvar" style="font-style:italic;">X Y</span> in <span class="texhtml mvar" style="font-style:italic;">α</span>

<ul><li>add(RelationTable, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\doteq Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\doteq Y}</annotation>

</semantics>

</math></span><img src="./4472d53defd4e68ec562a0f3befd92fdffc030a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.852ex; height:2.176ex;" alt="{\displaystyle X\doteq Y}" loading="lazy"></span>)</li>

<li>add(RelationTable, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}</annotation>

</semantics>

</math></span><img src="./d20e0147c4393fa27306d78741bfcfd419ace78d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.402ex; height:3.009ex;" alt="{\displaystyle X\lessdot \mathrm {Head} ^{+}(Y)}" loading="lazy"></span>)</li>

<li>add(RelationTable, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}</annotation>

</semantics>

</math></span><img src="./5eb243ade73a19be47a4feb84b5b3d935f9ca246.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.4ex; height:3.009ex;" alt="{\displaystyle \mathrm {Tail} ^{+}(X)\gtrdot \mathrm {Head} ^{*}(Y)}" loading="lazy"></span>)</li></ul></li></ul></li>

<li>add(RelationTable, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}</annotation>

</semantics>

</math></span><img src="./7c724539ba33c34d8e9e12e7ff3394ef381839fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.311ex; height:3.009ex;" alt="{\displaystyle \$\lessdot \mathrm {Head} ^{+}(S)}" loading="lazy"></span>) where <span class="texhtml mvar" style="font-style:italic;">S</span> is the initial non terminal of the grammar, and $ is a limit marker</li>

<li>add(RelationTable, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}</annotation>

</semantics>

</math></span><img src="./b2c8cd09755e11b5e85a5480db33f5622b6a121c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.214ex; height:3.009ex;" alt="{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \$}" loading="lazy"></span>) where <span class="texhtml mvar" style="font-style:italic;">S</span> is the initial non terminal of the grammar, and $ is a limit marker</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lessdot }</annotation>

</semantics>

</math></span><img src="./48abe158799d6c5ee0a960cec7e5321a5bf0ad61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \lessdot }" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gtrdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gtrdot }</annotation>

</semantics>

</math></span><img src="./7ade4309e8e12df271a3a66cda676411771e74fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \gtrdot }" loading="lazy"></span> are used with sets instead of elements as they were defined, in this case you must add all the <a href="Cartesian_product" title="Cartesian product">cartesian product</a> between the sets/elements.</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Example_1">Example 1</h3></div>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to aSSb|c}</annotation>

</semantics>

</math></span><img src="./1951c04855860daff1bdd5d194e82fcb3aa40387.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.993ex; height:2.843ex;" alt="{\displaystyle S\to aSSb|c}" loading="lazy"></span>

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to aSSb}</annotation>

</semantics>

</math></span><img src="./08e33e7fef7a0f483bebb9c9b3ccc97f0c80f3b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.339ex; height:2.176ex;" alt="{\displaystyle S\to aSSb}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\doteq S}</annotation>

</semantics>

</math></span><img src="./d26befcb5272d33fbe6efba8828c7bdb6513558f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.828ex; height:2.176ex;" alt="{\displaystyle a\doteq S}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}</annotation>

</semantics>

</math></span><img src="./4e4887ed214af59dbc1515e1b3fa45157eb7d07d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.378ex; height:3.009ex;" alt="{\displaystyle a\lessdot \mathrm {Head} ^{+}(S)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\lessdot a}</annotation>

</semantics>

</math></span><img src="./a87fcc13f097a85618bf123df91b75564ff2ad89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.558ex; height:1.843ex;" alt="{\displaystyle a\lessdot a}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\lessdot c}</annotation>

</semantics>

</math></span><img src="./0a25284b5bb9577600be3b530b19081ad62dd5d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.335ex; height:1.843ex;" alt="{\displaystyle a\lessdot c}" loading="lazy"></span></li></ul></li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\doteq S}</annotation>

</semantics>

</math></span><img src="./5cddbe5aa9d60509aef3b30a1ac5cef0ad4c2141.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.097ex; height:2.176ex;" alt="{\displaystyle S\doteq S}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}</annotation>

</semantics>

</math></span><img src="./d17d4afcddc00b499cad4386defa3cff3b527678.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.647ex; height:3.009ex;" alt="{\displaystyle S\lessdot \mathrm {Head} ^{+}(S)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\lessdot a}</annotation>

</semantics>

</math></span><img src="./4509e120cb8c81c346c69497c02c7bb0c659f048.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.828ex; height:2.176ex;" alt="{\displaystyle S\lessdot a}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\lessdot c}</annotation>

</semantics>

</math></span><img src="./daa67c7cdc156869102ba0d2dfd0a39b2f38a7bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.605ex; height:2.176ex;" alt="{\displaystyle S\lessdot c}" loading="lazy"></span></li></ul></li>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}</annotation>

</semantics>

</math></span><img src="./f33f794db0357ada91976ad64468baa926ae2608.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.645ex; height:3.009ex;" alt="{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(S)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\gtrdot a}</annotation>

</semantics>

</math></span><img src="./9dba2caab3df71bca97af14db896ead979c5650c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b\gtrdot a}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\gtrdot c}</annotation>

</semantics>

</math></span><img src="./3d046ff057ddf0e85631f1e20fd8aa7a41611160.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.103ex; height:2.176ex;" alt="{\displaystyle b\gtrdot c}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\gtrdot a}</annotation>

</semantics>

</math></span><img src="./e95b87381631164a4b900dfe0d4215d7f94cc996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.335ex; height:1.843ex;" alt="{\displaystyle c\gtrdot a}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\gtrdot c}</annotation>

</semantics>

</math></span><img src="./4d5a730aea6ee52fdee265b3fbaff39df4c380ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.112ex; height:1.843ex;" alt="{\displaystyle c\gtrdot c}" loading="lazy"></span></li></ul></li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\doteq b}</annotation>

</semantics>

</math></span><img src="./325f36da5dc10e324e2d6f3adffc73ac6325f168.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.595ex; height:2.176ex;" alt="{\displaystyle S\doteq b}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}</annotation>

</semantics>

</math></span><img src="./9c698845651291bc3534c2f0b45690a7516f362b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.144ex; height:3.009ex;" alt="{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(b)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\gtrdot b}</annotation>

</semantics>

</math></span><img src="./5921c2d843655ff8163fbd58dbfbc74a3e014239.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.094ex; height:2.176ex;" alt="{\displaystyle b\gtrdot b}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\gtrdot b}</annotation>

</semantics>

</math></span><img src="./bba94ca44f72a1817bff63328e416dbbf6b80a11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.103ex; height:2.176ex;" alt="{\displaystyle c\gtrdot b}" loading="lazy"></span></li></ul></li></ul></li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to c}</annotation>

</semantics>

</math></span><img src="./4723bbd12efb1ee080f493383ab8b1af18ba6f59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.12ex; height:2.176ex;" alt="{\displaystyle S\to c}" loading="lazy"></span>

<ul><li>there is only one symbol, so no relation is added.</li></ul></li></ul>

<dl><dt>precedence table</dt>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}</annotation>

</semantics>

</math></span><img src="./8778fc5da10445c0291caf3578fc743a33a36c54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.505ex; width:24.762ex; height:20.176ex;" alt="{\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&\doteq &\lessdot &\doteq &\lessdot &\\a&\doteq &\lessdot &&\lessdot &\\b&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Example_2">Example 2</h3></div>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to a|aT|[S]}</annotation>

</semantics>

</math></span><img src="./56e3446f56012d2e8b6dbcc51d57ec030a338dcd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.296ex; height:2.843ex;" alt="{\displaystyle S\to a|aT|[S]}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\to b|bT}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\to b|bT}</annotation>

</semantics>

</math></span><img src="./074728942e68053a9a65b0798a09c6e0aaf87d2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.529ex; height:2.843ex;" alt="{\displaystyle T\to b|bT}" loading="lazy"></span>

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to aT}</annotation>

</semantics>

</math></span><img src="./429605eed020af8de16a615d16e1b9d7ed185a46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.979ex; height:2.176ex;" alt="{\displaystyle S\to aT}" loading="lazy"></span></li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\doteq T}</annotation>

</semantics>

</math></span><img src="./b7762ef00577589384e2ec1cbbf144ce4fc575a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.965ex; height:2.176ex;" alt="{\displaystyle a\doteq T}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\lessdot \mathrm {Head} ^{+}(T)}</annotation>

</semantics>

</math></span><img src="./746bbb16282c007e9449f73fcd3cad6ee33628c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.515ex; height:3.009ex;" alt="{\displaystyle a\lessdot \mathrm {Head} ^{+}(T)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\lessdot b}</annotation>

</semantics>

</math></span><img src="./9721c53f2884b2702049a7d4e17b3ade3b21af37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a\lessdot b}" loading="lazy"></span></li></ul></li></ul></li></ul></li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\to [S]}</annotation>

</semantics>

</math></span><img src="./ee50b6958472283dfaa228f8c159ef586681b615.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.906ex; height:2.843ex;" alt="{\displaystyle S\to [S]}" loading="lazy"></span></li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\doteq S}</annotation>

</semantics>

</math></span><img src="./f48c9b621adcf63d1d2229af2f0a721c0cde5c9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.599ex; height:2.843ex;" alt="{\displaystyle [\doteq S}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\lessdot \mathrm {Head} ^{+}(S)}</annotation>

</semantics>

</math></span><img src="./84973737effb48719f804ab308cb28172e9bd03d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.15ex; height:3.009ex;" alt="{\displaystyle [\lessdot \mathrm {Head} ^{+}(S)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\lessdot a}</annotation>

</semantics>

</math></span><img src="./2cdc6ccb144c9839a177197ec317e8df71079ea5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.33ex; height:2.843ex;" alt="{\displaystyle [\lessdot a}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\lessdot [}</annotation>

</semantics>

</math></span><img src="./761af14aac8e3649bfb21f0cae0006b84afc10dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.102ex; height:2.843ex;" alt="{\displaystyle [\lessdot [}" loading="lazy"></span></li></ul></li></ul></li></ul></li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\doteq ]}</annotation>

</semantics>

</math></span><img src="./1284b981412a510b580c3dabfa7590a7bd7922dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.599ex; height:2.843ex;" alt="{\displaystyle S\doteq ]}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])}</annotation>

</semantics>

</math></span><img src="./2a49a4263e198f18e84bd2d758bd0513da1ba53a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.793ex; height:3.009ex;" alt="{\displaystyle \mathrm {Tail} ^{+}(S)\gtrdot \mathrm {Head} ^{*}(])}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\gtrdot ]}</annotation>

</semantics>

</math></span><img src="./5e458d62714aa1d5433e4a0484e435fd2297cc52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.33ex; height:2.843ex;" alt="{\displaystyle a\gtrdot ]}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\gtrdot ]}</annotation>

</semantics>

</math></span><img src="./52d9a2389ec97bb72f9357583dee6df843fd3714.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.736ex; height:2.843ex;" alt="{\displaystyle T\gtrdot ]}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ]\gtrdot ]}</annotation>

</semantics>

</math></span><img src="./6cb8652498bffd0605c33be702ff3a091dfa5c68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.102ex; height:2.843ex;" alt="{\displaystyle ]\gtrdot ]}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\gtrdot ]}</annotation>

</semantics>

</math></span><img src="./7b35535fcb3f2f5264e57af0ab7977dfd3af0257.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.098ex; height:2.843ex;" alt="{\displaystyle b\gtrdot ]}" loading="lazy"></span></li></ul></li></ul></li></ul></li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\to bT}</annotation>

</semantics>

</math></span><img src="./57355907e939d9a50a8e44c2c9282282bdc86821.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.884ex; height:2.176ex;" alt="{\displaystyle T\to bT}" loading="lazy"></span></li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\doteq T}</annotation>

</semantics>

</math></span><img src="./7722cd6535b56fc4f92ba59ca386c0788a5db1a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.732ex; height:2.176ex;" alt="{\displaystyle b\doteq T}" loading="lazy"></span></li>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\lessdot \mathrm {Head} ^{+}(T)}</annotation>

</semantics>

</math></span><img src="./82cbfe9eea89030bb06048bf4b495fa18cf90235.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.283ex; height:3.009ex;" alt="{\displaystyle b\lessdot \mathrm {Head} ^{+}(T)}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\lessdot b}</annotation>

</semantics>

</math></span><img src="./5a245ee7afa3ab5ac21e5caf90ae84affb908df0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.094ex; height:2.176ex;" alt="{\displaystyle b\lessdot b}" loading="lazy"></span></li></ul></li></ul></li></ul></li></ul>

<dl><dt>precedence table</dt>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}}</annotation>

</semantics>

</math></span><img src="./b964c44c9fa0b977fba266f30211535bcfbed025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -12.838ex; width:33.161ex; height:26.843ex;" alt="{\displaystyle {\begin{array}{c|ccccccc}&S&T&a&b&[&]&\$\\\hline S&&&&&&\doteq &\doteq \\T&&&&&&\gtrdot &\gtrdot \\a&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\b&&\doteq &&\lessdot &&\gtrdot &\gtrdot \\{\text{[}}&\doteq &&\lessdot &&\lessdot &&\\]&&&&&&\gtrdot &\gtrdot \\\$&\doteq &&\lessdot &&\lessdot &&\end{array}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972.</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFClaude_Pair1964" class="citation journal cs1">Claude Pair (1964). "Arbres, piles et compilation". <i>Revue française de traitement de l'information</i>.</cite>, in English <i>Trees, stacks and compiling</i></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation cs2"><span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/machineslanguage00denn"><i>Machines, Languages, and Computation</i></a></span>, <a href="Prentice%E2%80%93Hall" class="mw-redirect" title="Prentice–Hall">Prentice–Hall</a>, 1978, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780135422588</bdi>, <q>Wirth and Weber [1966] generalized Floyd's precedence grammars, obtaining the simple precedence grammars.</q></cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Alfred V. Aho, Jeffrey D. Ullman (1977). <i>Principles of Compiler Design</i>. 1st Edition. Addison–Wesley.</li>

<li>William A. Barrett, John D. Couch (1979). <i>Compiler construction: Theory and Practice</i>. Science Research Associate.</li>

<li>Jean-Paul Tremblay, P. G. Sorenson (1985). <i>The Theory and Practice of Compiler Writing</i>. McGraw–Hill.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFAhoUllman" class="citation cs2">Aho, Alfred V.; Ullman, Jeffrey D., <i>The theory of parsing, translation, and compiling</i></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cs.clemson.edu/course/cpsc827/material/Simple%20Precedence/Relations.pdf">"Simple Precedence Relations"</a> at Clemson University</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parsing_algorithms116" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parsing_algorithms116" style="font-size:114%;margin:0 4em"><a href="Parsing" title="Parsing">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Top-down_parsing" title="Top-down parsing">Top-down</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Earley_parser" title="Earley parser">Earley</a></li>

<li><a href="Recursive_descent_parser" title="Recursive descent parser">Recursive descent</a>

<ul><li><a href="Tail_recursive_parser" title="Tail recursive parser">Tail recursive</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Bottom-up_parsing" title="Bottom-up parsing">Bottom-up</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Precedence

<ul><li><a href="Simple_precedence_parser" class="mw-redirect" title="Simple precedence parser">Simple</a></li>

<li><a href="Operator-precedence_parser" title="Operator-precedence parser">Operator</a>

<ul><li><a href="Shunting_yard_algorithm" title="Shunting yard algorithm">Shunting-yard</a></li></ul></li></ul></li>

<ul><li><a href="Simple_LR_parser" title="Simple LR parser">Simple</a></li>

<li><a href="LALR_parser" title="LALR parser">Look-ahead</a></li>

<li><a href="Canonical_LR_parser" title="Canonical LR parser">Canonical</a></li>

<li><a href="GLR_parser" title="GLR parser">Generalized</a></li></ul></li>

<li><a href="Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent</a></li>

<li><a href="Shift-reduce_parser" title="Shift-reduce parser">Shift-reduce</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mixed, other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parser_combinator" title="Parser combinator">Combinator</a></li>

<li><a href="Chart_parser" title="Chart parser">Chart</a>

<ul><li><a href="Left_corner_parser" title="Left corner parser">Left corner</a></li></ul></li>

<li>Statistical</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>

<li><a href="Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Memoization" title="Memoization">Memoization</a></li>

<li><a href="Compiler-compiler" title="Compiler-compiler">Parser generator</a>

<li><a href="Parse_tree" title="Parse tree">Parse tree</a></li>

<li><a href="Scannerless_parsing" title="Scannerless parsing">Scannerless parsing</a></li>

<li><a href="History_of_compiler_construction" title="History of compiler construction">History of compiler construction</a></li>

<li><a href="Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></li>

<li><a href="Operator-precedence_grammar" title="Operator-precedence grammar">Operator-precedence grammar</a></li></ul>

</div></td></tr></tbody></table></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style>

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-29" href="https://en.wikipedia.org/wiki/?title=Simple_precedence_parser&oldid=1292969158">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>